package org.example;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Test4 {
    //leetcode 144 https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

    /**
     * 非递归方式实现二叉树的前序遍历
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> ret = new ArrayList<>();
        if (root == null) return ret;
        while (!stack.empty() || root != null) {
            while (root != null) {
                stack.add(root);
                ret.add(root.val);
                root = root.left;
            }
            root = stack.pop().right;
        }
        return ret;
    }

    public static void main(String[] args) {
        Test4 test4 = new Test4();
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        a.right = b;
        b.left = c;
        test4.preorderTraversal(a);
        System.out.println(666);
    }
}
